package year2019.month12;

//import java.io.

//快速排序
public class QuickSort {

    public static void main(String[] args) {
        int arr[] = new int[]{30,3,34,17,90,44,46,34,31,1,39,7,91,24,56};
        int len = arr.length-1;
        arr = sort(arr,0,len);
        for (int i:arr) {
            System.out.print(i+"\t");
        }
    }

    public static int[] sort(int arr[],int start,int end) {
        int pivot = arr[start];
        int left = start;
        int right = end;
        while (left<right) {
            while ((left<right) && (arr[right]<pivot)) {     //先从右往左比较，如果找到比基准数小的数字，跳出循环
                right--;
            }
            while ((left<right) && (arr[left]>pivot)) {      //再从左往右比较，如果找到比基准数大的数字，跳出循环
                left++;
            }
            if (left==right) {      //如果左右指针相同，则将基准数与指针上的数字交换
                arr[start] = arr[left];
                arr[left] = pivot;
            } else {                //通常情况则交换左右指针上的数字
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        if (left-1>start) arr = sort(arr, start, left-1);
        if (right+1<end) arr = sort(arr, right+1, end);
        return (arr);
    }

}
